// 单链表CRUD
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 全局变量
int ARRAY[MAX_SIZE];
int ARRAY_LEN = 0;

/**
 * @param  单链表头结点的引用
 * @author wxc
 * @Description: 初始化单链表
 */
void initList(LinkList *L) {
    LNode *s = (LNode *) malloc(sizeof(LNode));
    // 头结点数据用来记录链表的长度(不包括头结点)
    s->data = 0;
    s->next = NULL;

    *L = s;
}

/**
 * @param 单链表头结点
 * @author wxc
 * @return  1 || 0
 * @Description: 判断单链表是否为空,1表示为空,0表示不为空
 */
int isEmpty(LinkList L) {
    return L->next == NULL ? 1 : 0;
}

/**
 * @param 单链表头结点的引用L 位序i 元素e
 * @author wxc
 * @Description: 在表L的第i个位置插入元素e(按位序)
 */
void insert(LinkList *L, int i, int e) {
    LNode *p;
    LNode *s = *L;
    if (i <= 0) return;

    // 头结点 -> 0 -> 1 -> 2 -> 3
    // 假设i = 2,那么需要遍历到 0,在 0 之后插入
    while (i != 1 && s->next != NULL) {
        i--;
        s = s->next;
    }

    p = (LNode *) malloc(sizeof(LNode));
    p->data = e;
    p->next = s->next;
    s->next = p;
    // 头结点值 ++
    ++((*L)->data);
}

/**
 * @param 单链表头结点的引用L 位序i
 * @author wxc
 * @Description: 在表L的第i个位置的元素(按位序)
 */
void deleteByIndex(LinkList *L, int i) {
    LNode *s = *L;
    if(i <= 0) return;
    while (i != 1 && s->next != NULL) {
        i--;
        s = s->next;
    }
    if(s->next == NULL) return;
    s->next = s->next->next;
}

/**
 * @param 单链表头结点的引用L 传入的数组arr 数组长度n
 * @author wxc
 * @Description: 头插法创建单链表,根据传入的数组创建，n是数组长度
 */
void createByHead(LinkList *L,int arr[],int n) {
    LNode *s;
    int i;
    for (i = 0; i < n; ++i) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = arr[i];
        s->next = (*L)->next;
        (*L)->next = s;
    }
    (*L)->data += n;
}

/**
 * @param 单链表头结点的引用L 传入的数组arr 数组长度n
 * @author wxc
 * @Description: 尾插法创建单链表,根据传入的数组创建，n是数组长度
 */
void createByTail(LinkList *L,int arr[],int n) {
    int i = 0;
    LNode *p = (*L);
    LNode *s;
    // 获得尾指针
    while(p->next != NULL) p = p->next;

    for (i = 0; i < n; ++i) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = arr[i];
        s->next = NULL;
        p->next = s;
        p = s;
    }
    (*L)->data += n;
}

/**
 * @param 单链表头结点L
 * @author wxc
 * @Description: 打印单链表
 */
void printList(LinkList L) {
    LNode *p = L->next;
    while(p != NULL) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * @param 单链表头结点L
 * @author wxc
 * @return  单链表长度
 * @Description: 获得单链表长度
 */
int listLength(LinkList L) {
    return L->data;
}

/**
 * @author wxc
 * @Description: 键盘输入填充 ARRAY
 */
void inputArr() {
    int tempData;
    while(1) {
        scanf("%d", &tempData);
        ARRAY[ARRAY_LEN++] = tempData;
        if (getchar() == '\n') {
            break;
        }
    }
}

/**
 * @param 单链表头结点的引用L 标志flag
 * @author wxc
 * @Description: 单链表排序,0表示从小到大排,1表示从大到小排，方便起见就用冒泡了
 */
void BubbleSort(LinkList *L,int flag) {
    LNode *firstNode = (*L)->next;
    int temp;
    // 需要排序的次数
    int count = (*L)->data - 1;
    while (count >= 1) {
        while (firstNode->next != NULL) {
            // 从小到大排序
            if (firstNode->data > firstNode->next->data && !flag) {
                // 交换 data
                temp = firstNode->data;
                firstNode->data = firstNode->next->data;
                firstNode->next->data = temp;
            }
            // 从大到小排序
            if (firstNode->data < firstNode->next->data && flag) {
                // 交换 data
                temp = firstNode->data;
                firstNode->data = firstNode->next->data;
                firstNode->next->data = temp;
            }
            firstNode = firstNode->next;
        }
        firstNode = (*L)->next;
        count--;
    }
}

/**
 * @param 单链表头结点L1 单链表头结点L2
 * @author wxc
 * @return  合并后单链表头结点L
 * @Description: 合并两个有序的单链表
 */
LinkList ListMerge(LinkList L1, LinkList L2) {
    LNode *pa, *pb, *pc, *L;
    L = (LNode *) malloc(sizeof(LNode));
    pa = L1->next;
    pb = L2->next;
    pc = L;
    while (pa && pb) {
        if (pa->data >= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;

    return L;
}

int main() {

    // 初始化链表头结点
    LinkList L;
    // 初始化单链表
    initList(&L);
    inputArr();

    // 头插法
    // createByHead(&L,ARRAY,ARRAY_LEN);
    // 尾插法
    createByTail(&L,ARRAY,ARRAY_LEN);

    // 删除结点
    // deleteByIndex(&L,3);
    // 添加结点
    // insert(&L,1,10);

    // 单链表排序
    // BubbleSort(&L,0);


    // 打印单链表
       printList(L);
    // 打印单链表长度
    // printf("%d",listLength(L));

    return 0;
}